#include <algorithm>
#include <iostream>
#include <map>
#include <vector>


using namespace std;

// 给你一个字符串 s，找到 s 中最长的回文子串。

class Solution {
public:
    string longestPalindrome(string s) {
        int idx = -1;
        int max = 0;

        for (int i = 0; i < s.size(); ++i) {
            // odd
            int offset = 0;
            while (i - (offset + 1) >= 0 && i + (offset + 1) < s.size() &&
                   s[i - (offset + 1)] == s[i + (offset + 1)]) {
                offset++;
            }

            // even
            int offset2 = -1;
            while (i - (offset2 + 1) >= 0 && i + 1 + (offset2 + 1) < s.size() &&
                   s[i - (offset2 + 1)] == s[i + 1 + (offset2 + 1)]) {
                offset2++;
            }

            int len = std::max(offset * 2 + 1, offset2 * 2 + 2);
            if (len > max) {
                idx = i;
                max = len;
            }
        }

        if (idx < 0) {
            return std::string();
        }
        return s.substr(idx + 1 - (max + 1) / 2, max);
    }
};

int main(int argc, char *argv[]) {
    std::cout << Solution().longestPalindrome("abbc") << std::endl;
    return 0;
}